package ljl.alg.jianzhioffer.round3.medium;

import java.util.HashSet;
import java.util.PriorityQueue;
import java.util.Set;

public class _49_nthUglyNumber {

    class lufei_dp {
        public int nthUglyNumber(int n) {
            int a = 0, b = 0, c = 0;
            int[] dp = new int[n];
            dp[0] = 1;
            for(int i = 1; i < n; i++) {
                int n2 = dp[a] * 2, n3 = dp[b] * 3, n5 = dp[c] * 5;
                dp[i] = Math.min(Math.min(n2, n3), n5);
                if(dp[i] == n2) a++;
                if(dp[i] == n3) b++;
                if(dp[i] == n5) c++;
            }
            return dp[n - 1];
        }
    }

    public class min_heap {
        public int nthUglyNumber(int n) {
            int[] facs = {2, 3, 5};
            PriorityQueue<Long> q = new PriorityQueue<>();
            q.offer(1L);
            Set<Long> seen = new HashSet<>();
            long res = 1;
            for (int i = 0; i < n; i++) {
                res = q.poll();
                for (int fac : facs) {
                    long next = fac * res;
                    if (seen.add(next))
                        q.offer(next);
                }
            }
            return (int)res;
        }
    }

}
